#include <SlabAllocator.h>
#include <RadixTree.h>


SlabAllocator *radixTreeNodeAllocator;



uint32 RadixTree::growTree(uint32 nr){
	uint32 i;
	RadixTreeNode *nhead;
	if(head == NULL){
		height += nr;
		head = new(RTNALLOC) RadixTreeNode();
	}else{
		for(i = 0; i < nr; i++){
			nhead = new(RTNALLOC) RadixTreeNode();
			if(nhead){
				nhead->el[0] = (addr_t *)head;
				if(head) nhead->ppSize(1);
				head = nhead;
				height++;
			}else{
				return 0;
			}
		}
	}
	return 1;
}

uint32 RadixTree::getHeight(uint32 index){
	uint32 hgh = 0;
	uint32 i = index >> 30;
	if(i){
		hgh = 6;
	}else{
		int32 j;
		for(j = 24, hgh = 5; j >= 0; j -= 6, --hgh){
			i = (index >> j) & 0x3f;
			if(i) break;
		}
	}
	if(!hgh) hgh = 1;//Если индекс равен 0
	return hgh;
}

void RadixTree::insertNode(uint32 index, void *elm){
	uint32 hgh = getHeight(index), idx;
	int32 i;
	kprintf("HGH:%i\n", hgh);
	if(hgh > height){
		growTree(hgh - height);
	}
	if(!head) head = new(RTNALLOC) RadixTreeNode();
	RadixTreeNode *cur = head;
	if(height > 1){
		for(i = height - 1; i > 0; --i){
			idx = (index >> (6 * i)) & 0x3f;
			if(!cur->el[idx]){
				cur->el[idx] = new(RTNALLOC) RadixTreeNode();
				cur->ppSize(1);
			}
			cur = (RadixTreeNode *)cur->el[idx];
		}
	}
	cur->el[index & 0x3f] = elm;
	cur->ppSize(1);
}

void * RadixTree::getNode(uint32 index){
	if(!height) return NULL;
	uint32 hgh = getHeight(index), idx;
	int32 i;
	if(hgh <= height){
		RadixTreeNode *cur = head;
		for(i = height - 1; i > 0; i--){
			idx = (index >> (6 * i)) & 0x3f;
			if(!cur->el[idx]) return NULL;
			cur = (RadixTreeNode *)cur->el[idx];
		}
		return cur->el[index & 0x3f];
	}
	return NULL;
}

uint32 radix_path[6];
uint32 RadixTree::removeNode(uint32 index){
	uint32 hgh = getHeight(index), j, idx, r;
	int32 i;
	RadixTreeNode **path = (RadixTreeNode **)radix_path;
	if(hgh <= height){
		RadixTreeNode *cur = head;
		path[0] = cur;
		for(i = height - 1, j = 1; i > 0; --i, ++j){
			idx = (index >> (6 * i)) & 0x3f;
			if(!cur->el[idx]) return 1;
			cur = (RadixTreeNode *)cur->el[idx];
			path[j] = cur;
		}
		for(i = j - 1, r = 0; i >= 0; --i, ++r){
			idx = (index >> (6 * r)) & 0x3f;
			path[i]->el[idx] = NULL;
			path[i]->mmSize(1);
			if(path[i]->getSize() == 0){
				//destroy(path[i], RTNALLOC);
				RTNALLOC->sa_mfree(path[i]);
				if(path[i] == head){head = NULL; height = 0;}
				continue;
			}
			break;
		}
	}
	return 0;
}



void RadixTree::printTree(){
	uint32 i;
	RadixTreeNode *cur = head;
	if(cur){
		cur->printNode();
		for(i = 0; i < 64; ++i){
			if(cur->el[i]){
			kprintf("\n");
				((RadixTreeNode *) cur->el[i])->printNode();
			}		
		}
	}else{
		kprintf("Tree is empty\n");
	}
}
